import numpy as np
import pandas as pd

file_path = "Data.txt"
out_path = "matrix_result.txt"

# 设置输出格式
np.set_printoptions(precision=16)

# 确定文件中的记录数量，节点数量以及标号
data_set = set()
data = pd.read_csv(file_path, delim_whitespace=True, header=None)
rows = data.shape[0]
columns = data.shape[1]
for i in range(rows):
    for j in range(columns):
        data_set.add(data.iloc[i, j])

data_list = list(data_set)
length = len(data_list)
maximum = max(data_list)
minimum = min(data_list)
print("line number:", rows) # 记录数量
print("Length:", length) # 节点数量
print("Maximum:", maximum) # 最大标号
print("Minimum:", minimum) # 最小标号

# 构建转移矩阵
adjacent_matrix = np.zeros((length, length))
transition_matrix = np.zeros((length, length))

for i in range(rows):
    column = data.iloc[i, 0] - 1
    row = data.iloc[i, 1] - 1
    adjacent_matrix[row, column] = 1

column_sum = np.sum(adjacent_matrix, axis=0)
dead_node = []

for i in range(adjacent_matrix.shape[1]):
    if column_sum[i] != 0:
        transition_matrix[:, i] = adjacent_matrix[:, i] / column_sum[i]
    else:
        transition_matrix[:, i] = adjacent_matrix[:, i]
        dead_node.append(i + 1)

print("dead node num:", len(dead_node))

# 迭代过程
length = transition_matrix.shape[1]
PR_matrix = np.ones((length, 1)) / length
teleport_param = 0.85
epsilon=1e-8

# 修正dead node
correction_matrix_dead = np.zeros_like(transition_matrix)
transition_matrix_old = transition_matrix.copy()

for i in range(len(dead_node)):
    for j in range(length):
        correction_matrix_dead[j, dead_node[i] - 1] = 1 / length

transition_matrix = transition_matrix + correction_matrix_dead

# 修正spider node
correction_matrix_spider = np.zeros_like(transition_matrix) 
flag = False # 判断是否有spider node
for i in range(length):
    if transition_matrix_old[i,i]==1:
        flag = True
        break

if(flag):
    correction_matrix_spider = np.ones((length, length)) / length
    transition_matrix = teleport_param*transition_matrix + (1-teleport_param)*correction_matrix_spider

#迭代过程
while True:
    PR_matrix_old = PR_matrix.copy()
    PR_matrix = np.dot(transition_matrix, PR_matrix_old)

    # 判断是否收敛
    error = np.abs(PR_matrix - PR_matrix_old).sum()
    if error < length*epsilon:
        break

result = {}
for i in range(PR_matrix.shape[0]):
    result[str(i+1)] = PR_matrix[i][0]

result_sorted = sorted(result.items(), key = lambda x:x[1], reverse = True)
with open(out_path, 'w') as file:
    for i in range(100):
        file.write(result_sorted[i][0])
        file.write(' ')
        file.write(str(result_sorted[i][1]))
        file.write('\n')
        print(result_sorted[i])